1. Field of the Invention
The present invention relates to a method and an apparatus for selecting test sequences, and in particular to a method and an apparatus for selecting test sequences in a software which has a specification prescribed by state transitions.
2. Description of the Related Art
In recent years, the selection of test sequences in testing a software which has a specification prescribed by state transitions has been generally performed by manual works. A procedure for such a manual selection of test sequences will be described referring to FIGS. 22-25.
A specification prescribed by state transitions can be composed of the combination of a preceding state Sx, an event Ey, and a subsequent state Sx+1 as shown in FIG. 22.
FIG. 23 illustrates an example of a telephone specification, as a general one, which is composed of the combination of the state transitions.
A state of xe2x80x9cidlexe2x80x9d (S10) in which a receiver is hanged up is an initial state (=preceding state). If an event of xe2x80x9coff-hookxe2x80x9d (E10) in which the receiver is picked up occurs, the preceding state (=present state) has a transition to a state of xe2x80x9cdial tonexe2x80x9d (S20) (=subsequent state).
This is one example of a state transition.
When the receiver is hanged up in the state of xe2x80x9cdial tonexe2x80x9d (S20), an event of xe2x80x9con-hookxe2x80x9d (E22) occurs and the present state returns to the initial state (S10). If ordinary numerals are dialed (E20) in the state of xe2x80x9cdial tonexe2x80x9d (S20), the present state has a transition to a state of xe2x80x9ccallxe2x80x9d (S30). If the call is not answered from the other end of the line, the present state returns to the initial state (S10) through an event of xe2x80x9con-hookxe2x80x9d (E31). If the call is answered through an event of xe2x80x9cresponsexe2x80x9d (E30), the present state has a transition to a state of xe2x80x9ccommunicationxe2x80x9d (S40), and if an event of xe2x80x9con-hookxe2x80x9d (E40) occurs after the state of xe2x80x9ccommunicationxe2x80x9d, the present state returns to the initial state (S10).
If special numerals such as xe2x80x9c100xe2x80x9d are dialed (E21) in the state of xe2x80x9cdial tonexe2x80x9d (S20), the present state has a transition to a state of xe2x80x9cspecial callxe2x80x9d (S50). If the call is answered through an event of xe2x80x9cresponsexe2x80x9d (E50), the present state has a transition to a state of xe2x80x9cspecial communicationxe2x80x9d (S60). In the state of xe2x80x9cspecial callxe2x80x9d or xe2x80x9cspecial communicationxe2x80x9d (S50 or S60), the communication line will not be released even if an event of xe2x80x9con-hookxe2x80x9d (E51 or E60) occurs. Instead, the present state has a transition to a state of xe2x80x9creservexe2x80x9d (S70). If a xe2x80x9ccompulsory callxe2x80x9d is answered back from the other end of the line (E70), the present state has a transition to a state of xe2x80x9creverse callxe2x80x9d (S80). If the call is answered through an event of xe2x80x9cresponsexe2x80x9d (E80), the present state returns to the state of xe2x80x9cspecial communicationxe2x80x9d (S60).
In the state of xe2x80x9cspecial communicationxe2x80x9d, xe2x80x9creservexe2x80x9d or xe2x80x9creverse callxe2x80x9d (S60, S70 or S80), if an event of xe2x80x9creleasexe2x80x9d (E61, E71 or E81) occurs, the present state returns to the initial state (S10).
An example of the specification having the combination of the state transitions in FIG. 23 is expressed in the form of a tree as shown in FIG. 24. It is to be noted that the events are omitted in FIG. 24. If the specification can be transformed into such a tree-structured combination of state transitions, test sequences can be extracted by adopting a pre-order traversal algorithm. The test sequences which can be extracted from the tree shown in FIG. 24 can be divided into six as shown in FIGS. 25A-25F.
Among the extracted test sequences, the selection of test sequences for which an actual test should be performed is done by an examiner in charge based on his experience. When selecting test sequences, it is general that all state transitions are tested at least once without omission in which a state transition in a normal mode which is called a xe2x80x9cmain sequencexe2x80x9d is preferentially tested with the combination of state transitions of xe2x80x9cillegal sequencesxe2x80x9d.
Such a manual selection of test sequences, when performed by an inexperienced examiner, may lead to a decrease in test efficiency due to selecting many unnecessary test sequences or to a decrease in test reliability due to failing to select necessary tests on the contrary. Also, even when performed by an experienced examiner, in case of a complicated system, the selection requires much time and causes human errors with a high possibility.
Specifically, a primary problem in the selection of test sequences arises when a specification composed of the combination of state transitions is transformed into a tree. Namely, although every node in a tree must have only one parent node, a specification composed of the combination of normal state transitions includes junctions (see {circle around (1)} in FIG. 23) in which a node has a plurality of parent nodes and loops (see {circle around (2)} in FIG. 23). Therefore, an experienced examiner is required to remove the junctions and the loops with appropriate means to transform the combination of state transitions into a tree-structure.
A secondary problem is that it is hard to appropriately select test sequences to be actually tested among all of the test sequences which can be extracted logically. Namely, since it is not practical to test all of the test sequences under the restrictions of a test term or man-hours, it is required to take time for sequentially selecting the test sequences to be actually tested in order of higher priority.
It is accordingly an object of the present invention to provide a method and an apparatus for transforming a given specification which is composed of the combination of state transitions into a tree-structure having removed therefrom junctions and loops, and for efficiently selecting appropriate test sequences.
[1] A method for selecting test sequences according to the present invention for the achievement of the above mentioned object, as schematically illustrated in FIG. 1, comprises a first step S1 for preparing tree-structured state transition data associated with state transition weights from state transition data, a second step S2 for extracting test sequences from the tree-structured state transition data, and a third step S3 for repeating processes of determining averaged weight for each of the test sequences, selecting a test sequence by which the average is maximum, and decrementing the weights contained in the selected test sequence by one unit to prioritize the test sequences.
Namely, in the first step S1, the tree-structured state transition data associated with state transition weights are prepared based on state transition data inputted as an aggregation of state transitions (see FIG. 22) and state transition weights which are inputted and set to have higher values for state transitions of more importance.
If the tree-structured state transition data are prepared, junctions and loops can be removed from the state transition data and all of the test sequences can be extracted. Therefore, in the second step S2, for example, a pre-order traversal algorithm is applied to the tree-structured state transition data, thereby extracting all of the test sequences.
For all of the test sequences extracted in the second the step S2, priorities among the test sequences are obtained in the third step S3.
Namely, in the third step S3, for all of the test sequences, the total of the state transition weights contained in each test sequence is divided by the number of the state transitions to obtain an averaged weight. The averaged weights for all of the test sequences are compared to one another, and the test sequence with the highest averaged weight is selected. Then the weights contained in the selected test sequence are decremented by one unit. Such processes are repeated until all priorities among the test sequences are determined.
Based on the priorities among the test sequences as obtained above, it is possible to omit unnecessary tests and perform only necessary tests, thus enabling an efficient selection of appropriate test sequences.
[2] In the above-mentioned invention [1], it is also possible for the third step S3 to further comprise a prioritizing step for retaining data indicating untested/tested state transitions and lowering the priority of the selected test sequence if all of the state transitions contained therein have been tested.
It is to be noted that the xe2x80x9cdata indicating untested/testedxe2x80x9d state transitions in the third step S3 are virtual information. Namely, assuming in the third step S3 that a test sequence is actually tested every time the priority of the test sequence is determined, since all of the state transitions are xe2x80x9cuntestedxe2x80x9d in the initial state but the test sequence is actually tested every time the priority of the test sequence is determined, all of the state transitions contained in the test sequence becomes xe2x80x9ctestedxe2x80x9d.
By retaining such data indicating xe2x80x9cuntestedxe2x80x9d or xe2x80x9ctestedxe2x80x9d state transitions, in the test sequence prioritizing step, if all of the state transitions contained in the selected test sequence are already tested, the priority of the test sequence can be lowered.
As a result, the frequency of repeatedly testing a tested state transition can be decreased, thereby enabling an efficient selection of test sequences.
[3] Also, a method for selecting test sequences according to the present invention may comprise a first step for preparing tree-structured state transition data associated with state transition weights from state transition data, a second step for extracting test sequences from the tree-structured state transition data, and a third step for retaining data indicating untested/tested state transitions to prioritize the test sequences based on the number of the untested state transitions.
Namely, in the third step S3, in order to obtain priorities among the test sequences, the data indicating untested/tested state transitions as described in the above-mentioned invention [2] are substituted for the averaged weight in the above-mentioned invention [1].
Then, the priorities among the test sequences are set so that the highest priority is set to a test sequence which contains the maximum number of the untested state transitions.
[4] Also, in the above-mentioned invention [3], if there are a plurality of test sequences containing the same number of the untested state transitions, the third step S3 may further comprise a step for prioritizing the test sequences based on the total of the weights.
Namely, in the third step S3, if there are a plurality of test sequences containing the maximum number of the untested state transitions, the prioritizing step sets the highest priority for the test sequence by which the total of the state transition weights is maximum among the plurality of test sequences.
[5] Also, the method in the above-mentioned invention [1] may further comprise a fourth step S4 for sequentially outputting a designated number of test sequences in order of higher priority.
Namely, in the fourth step S4, an examiner may designate a number of test sequences based on his experience or considering the man-hours allowed for the test, and the designated number of test sequences can be sequentially outputted in order of higher priority.
[6] Also, in the above-mentioned invention [5], if there are test sequences containing untested state transitions among the test sequences which are not included in the output by the fourth step S4, the method may further comprise a step for outputting the test sequences with warning messages.
Namely, by adding the step for outputting the test sequence, even if the number of outputting test sequences designated in the above-mentioned invention [5] is small, a principal condition that all of the state transitions are tested at least once without omission can be fulfilled.
[7] In the above-mentioned invention [5], it is also possible for the fourth step S4 to sequentially output only the number of test sequences containing untested state transitions instead of outputting the designated number of test sequences.
In the above-mentioned invention [5], the examiner designates the number of test sequences to be outputted based on his experience and the man-hours allowed for the test. However, there is a possibility that the examiner cannot specify an appropriate number due to lack of experience and the like.
Therefore, in the above-mentioned invention [7], by outputting only the test sequences which include untested state transitions, the primary condition that all of the state transitions are tested at least once without omission is fulfilled and the minimum of required test sequences can be outputted.
[8] An apparatus for realizing a method for selecting test sequences according to the present invention as shown in FIG. 1, is schematically shown in FIG. 2. As shown in FIG. 2, the apparatus comprises a tree-structure transformation portion P1 for preparing tree-structured state transition data F2 associated with state transition weights from state transition data F1, a test sequence extraction portion P2 for extracting test sequences from the tree-structured state transition data F2, and a priority decision portion P3 for repeating processes of determining averaged weight for each of the test sequences, selecting a test sequence by which the average is maximum, and decrementing the weights contained in the selected test sequence by one unit to prioritize the test sequences and enter them in a prioritized test sequence data F3.
Namely, in a tree-structure transformation portion P1, based on the state transition data F1 in which a state transition specification I1 is entered as an aggregation of state transitions (see FIG. 22) and state transition weights I2 which are set and entered with higher values for more important state transitions, the tree-structured state transition data F2 are prepared.
When the tree-structured state transition data F2 are prepared, junctions and loops can be removed from the state transition data and all of the test sequences can be extracted. Therefore, in the test sequence extraction portion P2, all of the test sequences are extracted by adopting, e.g. the pre-order traversal algorithm.
For all of the test sequences extracted in the test sequence extraction portion P2, the priorities among test sequences are determined in the priority decision portion P3.
Namely, in the priority decision portion P3, for all of the test sequences, processes are repeated for comparing the averaged weights determined by dividing the total of the state transition weights contained in each test sequence by the number of state transitions, selecting the test sequence by which the average is maximum, and decrementing the weights contained in the selected test sequence by one unit until all of the priorities among test sequences are determined.
Therefore, appropriate test sequences can be efficiently selected as in the above-mentioned invention [1].
[9] In the above-mentioned invention [8], it is also possible for the priority decision portion P3 to further comprise means for retaining data indicating untested/tested state transitions and lowering the priority of the selected test sequence if all of the state transitions contained therein have been tested.
The data indicating untested/tested state transitions retained in the priority decision portion P3 are as recited in the above-mentioned invention [2]. Therefore, by the means for lowering the priority, the frequency of repeatedly testing a tested state transition can be decreased, thereby enabling an efficient selection of test sequences.
[10] Also, an apparatus for selecting test sequences according to the present invention may comprise a tree-structure transformation portion P1 for preparing tree-structured state transition data F2 associated with state transition weights from state transition data F1, a test sequence extraction portion P2 for extracting test sequences from the tree-structured state transition data F2, and a priority decision portion P3 for retaining data indicating untested/tested state transitions to prioritize the test sequences based on the number of the untested state transitions and enter the test sequences in a prioritized test sequence data F3.
Namely, in the priority decision portion P3, in order to decide the priorities among each test sequence, the data indicating untested/tested state transitions as recited in the above-mentioned invention [9] are substituted for the averaged weight for state transitions as recited in the above-mentioned invention [8].
[11] In the above-mentioned invention [10], if there are a plurality of test sequences containing the same number of the untested state transitions, it is also possible for the priority decision portion P3 to further comprise means for prioritizing the test sequences based on the total of the weights.
Namely, in the priority decision portion P3, if there are a plurality of test sequences containing the maximum number of untested state transitions, the means for prioritizing the test sequences sets the highest priority for the test sequence by which the total of the state transition weights is the maximum among the plurality of test sequences.
[12] Also, in the above-mentioned inventions [8], the apparatus may further comprise an output portion P4 for sequentially outputting a designated number of test sequences in order of higher priority.
Namely, in the output portion P4, an examiner may designate a number of test sequences based on his experience or considering man-hours allowed for the test, and the designated number of test sequences can be sequentially outputted in order of higher priority.
[13] In the above-mentioned invention [12], if there are test sequences containing untested state transitions among the test sequences which are not included in the output by the output portion P4, the apparatus may further comprise means for outputting the test sequences with warning messages.
Namely, by adding the means for outputting the test sequences, even if the number of outputting test sequences designated in the above-mentioned invention [12] is small, the principal condition that all of the state transitions are tested at least once without omission can be fulfilled.
[14] In the above mentioned invention [12], it is also possible for the apparatus to further comprise means for sequentially outputting only the number of test sequences containing untested state transitions in order of higher priority.
In the above-mentioned invention [12], the examiner designates the number of test sequences to be outputted based on his experience and the man-hours allowed for the test. However, there is a possibility that the examiner cannot specify an appropriate number due to lack of experience and the like.
Therefore, in the above-mentioned invention [14], by outputting only the test sequences which include untested state transitions, the minimum test sequences can be outputted with the primary condition that all of the state transitions are tested at least once without omission being fulfilled.